package project2;

/*
* 2019-11-23
* 三取样切分，使用子数组的一小部分元素的中位数来切分数组
* 将取样大小设为3并用大小居中的元素来切分
* 算法表述：
* 从左到右遍历数组一次，维护
* 一个指针lt，使得a[lo..lt-1]中的元素都小于v，
* 一个指针gt使得a[gt+1..hi]中的元素都大于v，
* 一个指针i使得a[lt..i-1]中的元素都等于v,a[i..gt]中的元素都未确定
* a[i] < v  exch(a[lt],a[i])  lt++, i++
* a[i] > v  exch(a[gt],a[i])  gt--
* a[i] == v i++
* */
public class QD3P {
    public void sort(int[] a, int lo, int hi){
       if(hi <= lo) return;
       int lt = lo, i = lo+1, gt = hi;
       int v = a[lo];
       while (i <= gt){
           if(a[i] < v) exch(a, lt++, i++);
           else if(a[i] > v) exch(a, gt--, i);
           else i++;
       }
       sort(a, lo, lt-1);
       sort(a, gt+1, hi);
    }

    private void exch(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
